package com.yang.Offer;

/**
 * @Author: yang
 * @Description: 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 *
 * 本次可采用方法有
 * 哈希表统计法：遍历数组 nums ，用 HashMap 统计各数字的数量，即可找出 众数 。此方法时间和空间复杂度均为 O(N)O(N)O(N)
 *  Map<Integer, Integer> counts = new HashMap<Integer, Integer>();
 *  getOrDefault(Object key, V defaultValue) 意思就是当Map集合中有这个key时，就使用这个key对应的value值，如果没有就使用默认值defaultValue
 * 数组排序法： 将数组 nums 排序，数组中点的元素 一定为众数。
 * 摩尔投票法： 核心理念为 票数正负抵消 。此方法时间和空间复杂度分别为 O(N)O(N)O(N) 和 O(1)O(1)O(1) ，为本题的最佳解法。
 * @Date: Created in 17:46 2022/8/3
 * @Modified By:
 */
public class Offer39 {
    class Offer39Solution {
        public int majorityElement(int[] nums) {
            // 假设x = 0
            int x = 0;
            // 假设此时票数为0  如果票数为0会进行众数的重假设
            int count = 0;
            for(int num : nums){
                x = count == 0 ? num : x;
                if(num == x){
                    count ++;
                }else{
                    count --;
                }
            }
            return x;
        }
    }
}
